#!/usr/bin/env  python
"""
python graph
"""

__author__ = "lynn lin"
__license__ = "MIT"
__version__ = "1.0"

# imports my own datastrure
from stack import stack
from queue import queue

# import decimal module
from decimal import NaN



class graph(object):
    """
    directed graph class
    """
    def __initvar__(self):
        self.container = {}
        self.indegree  = {}
        self.outdegree = {}
        self.postfdn   = 0
        self.prefdn    = 0
        self.pre       = {}
        self.post      = {}
        self.toplist   = {}
# {'v1':{'v2':-1},'v2':{}}
        self.weight    = {}
        self.dist      = {}
# visited flag,default is unvisited 
        self.visited   = {}
    def __init__(self):
        """
        initial node list 
        """
        self.__initflag = False
        
        self.__initvar__()
        
    def __len__(self):
        """
        return number of graph nodes
        """
        return len(self.container.keys())
    
    def __initVisited(self):
        for v in self.container.keys():
            self.visited[v] = 0
            
    def addnode(self,node,arc = [],weight = []):
        if node not in self.container.keys():
            self.container[node] = arc
           # self.weight[node] = {}
            self.indegree[node] = 0
            self.outdegree[node] = 0
        else :
                 self.container[node] += arc
        for item in arc :
                if item not in self.container.keys():
                    self.container[item] = []
                    self.indegree[item] = 0
                    self.indegree[item] += 1
                    self.outdegree[node] += 1           
                    self.outdegree[item] = 0
                else :
                    self.indegree[item] += 1
                    self.outdegree[node] += 1

    def initWeight(self):
        if self.__initflag == False:
            self.__initflag = True
            for vetx in self.container.keys():
                self.weight[vetx] = {}
                self.dist[vetx] = NaN
            for vetx in self.container.keys():
                    for arc in self.container.keys():
                        if vetx == arc :
                            self.weight[vetx][arc] = 0
                            continue
                        self.weight[vetx][arc] = -1
    
    def addWeight(self,u,v,w):
#        self.initWeight()
#        self.weight[u][v] = w
         if v == None:
            self.weight[u] = {}
            self.dist[u] = NaN
            return
         if u not in self.weight.keys():
            self.weight[u] = {v:w}
            self.dist[u] = NaN
         else :
            self.weight[u][v] = w
        
    def delNode(self,node):
            if node not in self.container.keys():
                return
            else :
                self.container.pop(node)
# decrease outdegree 
                for v in self.container.keys():
                    if node in self.container[v]:
                        self.outdegree[v] -= 1
                        self.container[v].remove(node)
                
    
    def delEge(self,u,v):
        """
        del ege (u->v)
        """
        if u not in self.container.keys():
            return
        if v in self.container[u]:
            print 'deleting ege u->v...'
            self.container[u].remove(v)
            self.indegree[v] -=1
            self.outdegree[u] -= 1
        
    def getNodeArc(self,node):
        if node in self.container.keys():
            return self.container[node]

    def getNodeIndegree(self,node):
        if node in self.container.keys():
            return self.indegree[node]
        else :
            raise "node is not in graph"

    def getNodeOutdegree(self,node):
        if node in self.container.keys():
            return self.outdegree[node]
        else :
            raise "node is not in graph"

    def SearchPath(self,start,goal):
        def generate(path,goal,solns):
            state = path[-1]
            if state == goal:
                solns.append(path)
            else :
                for arc in self.container[state]:
                    if arc not in path:
                        generate(path + [arc],goal,solns)
        solns = []
        generate([start],goal,solns)
        solns.sort(lambda x,y:cmp(len(x),len(y)))
        return solns
    
    def Breadth_first_search(self):
        """
        using queue datastructure
        """
        for v in self.container.keys():
            self.visited[v] = 0
# initialize queue
        que = queue()
        for vetex in self.container.keys():
            if self.visited[vetex] == 0 :
                que.EnQueue(vetex)
            while que.QueueEmpty() > 0 :
                node = que.DeQueue()
                if self.visited[node] == 0 :
                    print 'node',node
                    self.visited[node] = 1
                for adj in self.container[node]:
                    if self.visited[adj] == 0 :
                        que.EnQueue(adj)
            
        
    def Depth_first_search(self):
        """
        using stack datastructure
        """
        for v in self.container.keys():
            self.visited[v] = 0
# initialize stack
        sta = stack()
        for vetex in self.container.keys():
            if self.visited[vetex] == 0 :
                sta.push(vetex)
            while sta.StackEmpty() > 0 :
                node = sta.pop()
                if self.visited[node] == 0 :
                    print 'node',node
                    self.visited[node] = 1
                for adj in self.container[node]:
                    if self.visited[adj] == 0 :
                        sta.push(adj)
        
    def dfs(self):
        """
        dfs using recurisive tech
        """
        def _dfs(v):
#            print v
            self.visited[v] = 1
            self.prefdn += 1
            self.pre[v] = self.prefdn
            for vetex in self.container[v]:
                if self.visited[vetex] == 0 :
                    _dfs(vetex)
            self.postfdn += 1
            self.post[v] = self.postfdn
        for v in self.container.keys():
         	self.visited[v] = 0
        for v in self.container.keys():
            if self.visited[v] == 0 :
                _dfs(v)

    def Top_Sort(self):
        """
        running is O(V*E)
        """
#    initialize topsort stack
        topstack = stack()
        for v in self.container.keys():
            if self.indegree[v] == 0 :
                topstack.push(v)
        count = 0
        R = {}
        while (topstack.StackEmpty() != 0):
            u = topstack.pop()
            count += 1
            R[count] = u
            for item in self.container[u]:
                self.indegree[item] = self.indegree[item] -1
                if self.indegree[item] == 0:
                    topstack.push(item)
        print R
        
    def Top_Sort2(self):
        self.dfs()
        return self.post
        
    def Shortest_Path(self,start):
        """
        unweighted shortest path
        """
        que = queue()
        path = {}
        path[start] = 0
        for vetx in self.container.keys():
            self.visited[vetx] = 0
        que.EnQueue(start)
        while (que.QueueEmpty() != 0):
            node = que.DeQueue()
            if self.visited[node] == 0 :
                self.visited[node] = 1
            for arc in self.container[node]:
                if self.visited[arc] == 0 :
                    path[arc] = path[node] + 1
                    que.EnQueue(arc)
        return path

# dijkstra algorithm to solve weighted shortest path problem
    def dijkstra(self,start):
        self.__initVisited()
        que = queue()
        que.EnQueue(start)
        self.dist[start] = 0
        while que.QueueEmpty() != 0 :
            node = que.DeQueue()
            if self.visited[node] == 0 :
                self.visited[node] = 1
            for arc in self.container[node]:
              #  print arc,self.dist[node],self.weight[node][arc],self.dist[arc]
                if self.dist[arc] == NaN :
                    self.dist[arc] = self.dist[node] + self.weight[node][arc]
                else:
                    if self.dist[node] + self.weight[node][arc] < self.dist[arc] :
                        self.dist[arc] = self.dist[node] + self.weight[node][arc]
                if self.visited[arc] == 0 :
                    que.EnQueue(arc)
        return self.dist
     
    def kruskal():
        pass
    
    def prim():
        pass
        
    def init_graph_test(self):
        G.addnode('v1',['v2','v4'])
        G.addnode('v2',['v4','v5'])
        G.addnode('v3',['v1','v6'])
        G.addnode('v4',['v3','v5','v6','v7'])
        G.addnode('v5',['v7'])
        G.addnode('v6',[])
        G.addnode('v7',['v6'])
        G.addWeight('v1','v2',2)
        G.addWeight('v1','v4',1)
        G.addWeight('v2','v4',3)
        G.addWeight('v2','v5',10)
        G.addWeight('v3','v1',4)
        G.addWeight('v3','v6',5)
        G.addWeight('v4','v3',2)
        G.addWeight('v4','v5',2)
        G.addWeight('v4','v6',8)
        G.addWeight('v4','v7',4)
        G.addWeight('v5','v7',6)
        G.addWeight('v6',None,None)
        G.addWeight('v7','v6',1)
   #     print G.dist
    
if __name__ == '__main__':
    G = graph()
    print '=================='
    G.init_graph_test()
    dis = G.dijkstra('v1') 
    print dis

     